# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random

"""
created by shhuan at 2017/9/24 09:55

"""


class Solution(object):
    def candyCrush(self, board):
        """
        :type board: List[List[int]]
        :rtype: List[List[int]]
        """



        m = len(board)
        n = len(board[0])

        crushed = True
        while crushed:
            # print("="*40)
            # for row in board:
            #     print(row)
            crushed = False
            X = set()
            for r in range(m):
                for c in range(n):
                    if board[r][c] == 0 or (r, c) in X:
                        continue
                    h = {(r, c)}
                    v = {(r, c)}
                    nr, nc = r, c
                    while 0 <= nr < m and 0 <= nc < n and board[nr][nc] == board[r][c]:
                        h.add((nr, nc))
                        nc += 1

                    nr, nc = r, c
                    while 0 <= nr < m and 0 <= nc < n and board[nr][nc] == board[r][c]:
                        v.add((nr, nc))
                        nr += 1

                    if len(h) >= 3:
                        X |= h
                        crushed = True
                    if len(v) >= 3:
                        X |= v
                        crushed = True

            for nr, nc in X:
                board[nr][nc] = 0

            cols = [[board[r][c] for r in range(m) if board[r][c] != 0] for c in range(n)]
            cols = [[0] * (m - len(col)) + col for col in cols]

            for c in range(n):
                for r in range(m):
                    board[r][c] = cols[c][r]

        return board

s = Solution()
print(s.candyCrush([[2,1,3],[2,2,2],[2,2,2]]))
print(s.candyCrush([[1,3,5,5,2],[3,4,3,3,1],[3,2,4,5,2],[2,4,4,5,5],[1,4,4,1,1]]))
# print(s.candyCrush([[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]))
# print([[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]])